/**
 * Copyright © 2021 易久批信息技术有限公司. All rights reserved.
 */
package com.dysm.search;

/**
 *
 * @author xiay
 * @since 2021/1/18 10:16 下午
 */
public class BinarySearchTest {

    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6,7,8,9,10};

        int key = 7;
//        int index = recursiveSearch(arr, key);
        int index = whileSearch(arr, key);
        System.out.println(index);

    }

    public static int whileSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == key) {
                return mid;
            }
            if (arr[mid] > key) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    public static int recursiveSearch(int[] arr, int key) {
        int low = 0;
        int high = arr.length -1;
        return recursive(arr, key, low, high);

    }

    private static int recursive(int[] arr, int key, int low, int high) {
        if (low > high) {
            return -1;
        }
        int mid = (low + high) / 2;
        if (arr[mid] == key) {
            return mid;
        }
        if (arr[mid] > key) {
            return recursive(arr, key, low, mid - 1);
        } else {
            return recursive(arr, key, mid + 1, high);
        }
    }

}
